/*
  Timeline
  题目描述
    Bessie 在过去的 M 天内参加了 N 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。
    对于第 i 次挤奶，Bessie 记得它不早于第 Si 天进行。
    另外，她还有 C 条记忆，每条记忆形如一个三元组 (a,b,x)，含义是第 b 次挤奶在第 a 次挤奶结束至少 x 天后进行。

    现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。
    保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：
      第 i 次挤奶不早于第 Si 天进行，且不晚于第 M 天进行；
      所有的记忆都得到满足；
  输入描述
    第一行三个整数 N, M, C。保证 1 ≤ N, C ≤ 10^5，2 ≤ M ≤ 10^9。
    接下来一行包含 N 个整数 S1, S2, … , Sn，保证 ∀1 ≤ i ≤ n，都满足 1 ≤ Si ≤ M。
    下面 C 行每行三个整数 a, b, x，描述一条记忆。保证 a ≠ b，且 1 ≤ x ≤ M。
  输出描述
    输出 N 行，每行一个整数，第 i 行的数表示第 i 次挤奶的最早日期。
  样例1
    输入
      4 10 3
      1 2 3 4
      1 2 5
      2 4 2
      3 4 4
    输出
      1
      6
      3
      8
  提示
    测试点 2∼4 满足 N, C ≤ 10^3。
    测试点 5∼10 没有特殊限制。
*/